In 944 kreeg de bisschop van Utrecht Balderik het jachtrecht in Vollenhove, in 1024 verwierf hij het graafschap Drenthe, waartoe dus ook het land van Vollenhove behoorde. Het was dan Balderik of zijn op volger die Steenwijk moet hebben gesticht. Er bestaat ook een legende over het ontstaan van Steenwijk, namelijk van drie kastelen aan de oevers van de Aa t.w. Oostwijk, Middelwijk en Westelijken . Het middelste slot was Middelwijk en deze naam zou veranderd zijn in Steenwijk. In 1141 bestond de Sint Clemenskerk al, deze was door de bisschop Hardbert al als kapittelkerk aangewezen voor het Land van Vollenhove, als onderdeel van de abdij van Ruinen. Vanuit de kapittelkerk werden parochies gesticht in Friesland en Drenthe. Aan de macht van bisschoppen werd nogal eens getwijfeld in die tijd. Er werd in 1229 een troepenmacht gestationeerd in Steenwijk, onder leiding van bisschop Wilbrand van Oldenburg. Deze moest het hoofd bieden aan nog geen verdedigingswerken in die tijd. In 1295 werd melding gemaakt van versterkte plaats Steenwijk (aarden wallen/ houten palissaden moet men dan aan denken.

Er werd begonnen met de aanleg van de gracht aan de zuidwest zijde. De Sint Clemens werd in 1500 afgebouwd in Steenwijk. Steenwijk werd onderdeel van het Oostenrijkse vorstenhuis de Habsburgers. Het huwelijk van Filips de Schone met de Spaanse koningsdochter Johanna waren grote delen van Europa onder één koningschap bij elkaar gebracht. Hun zoon Karel kreeg uiteindelijk de Nederlanden Oostenrijk, Spanje en Italië in één land. De installatie van Karel de V zorgde voor schermutselingen rond Steenwijk. De ligging van Steenwijk was om richting Friesland te gaan, dit was erg belangrijk. Hij werd krachtig tegen gewerkt door door de hertog Karel van Gelre. In 1522 werd door Cornelis van Meurs een poging ondernomen om de stad in te nemen. Vijfhonderd soldaten lieten het leven, maar de aanval werd afgeslagen.